/**
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输
出"student. a am I"。 

 

 示例 1： 

 输入: "the sky is blue"
输出: "blue is sky the"
 

 示例 2： 

 输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 

 示例 3： 

 输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 

 

 说明： 

 
 无空格字符构成一个单词。 
 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 
 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。 
 

 注意：本题与主站 151 题相同：https://leetcode-cn.com/problems/reverse-words-in-a-string/ 

 注意：此题对比原题有改动 

 Related Topics 双指针 字符串 👍 278 👎 0

*/

package com.shuzijun.leetcode.editor.cn;
public class FanZhuanDanCiShunXuLcof{
    public static void main(String[] args) {
         Solution solution = new FanZhuanDanCiShunXuLcof().new Solution();
        System.err.println(solution.reverseWords("hello world!"));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String reverseWords(String s) {
        char[] str = s.toCharArray();
        int n = trim(str);
        if (n == 0) {
            return "";
        }

        reverse(str,0,n-1);
        int p = 0;
        while (p < n){
            int r = p;
            while (r < n && str[r] != ' ') {
                r ++;
            }
            reverse(str,p,r -1);
            p = r+1;
        }

        char[] newStr = new char[n];
        for (int i = 0; i < n; i++) {
            newStr[i] = str[i];
        }
        return new String(newStr);
    }

        private void reverse(char[] str, int i, int j) {
            char tmp = str[i];
            str[i] = str[j];
            str[j] = tmp;
        }

        private int trim(char[] str) {
            int n =  str.length;
            int i = 0;
//            去除左侧/
            while (i<n && str[i] == ' ') {
                i++;
            }
//            去除右侧/
            int j =  n-1;
            while (j >= 0 && str[j] == ' '){
                j --;
            }

            int k = 0;
            while (i <= j) {
                if (str[i] == ' ') {
                    if (i+1 <= j && str[i+1] != ' '){
                        str[k++] = ' ';
                    }
                } else {
                    str[k++] = str[i];
                }
                i++;
            }

            return k;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}